﻿// 0831train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>

using namespace std;

/*
 小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。
k，t，n都是给定的。求出可行解数量。

输入描述
第一行输入 n t k，用空格进行分割
第二行输入 每个运动的卡路里 按照空格进行分割

输入
4 3 2
1 1 2 3
输出
2
可行解为2，选取{0,2}, {1,2}两种方式

输入
4 3 2 4_n总数  3_和为t 2_k个运动
1 1 2 3
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec, int amount, int limit)
    {
        // dp[dp_amount][k]=dp[dp_amount-curr][k-1]
        vector<vector<int>>dynamic_vec(amount + 1, vector<int>(limit + 1));

        //dp[0][0]=1 amount=0，只有选0个运动时是1
        dynamic_vec[0][0] = 1;
        //dp[r][0]=0 0个运动凑不出任何amount

        for (auto&curr:num_vec)
        {
            for (int dp_amount=amount; dp_amount>=1; dp_amount--)
            {
                for (int k=1; k<=limit; k++)
                {
                    if (dp_amount - curr < 0) continue;

                    dynamic_vec[dp_amount][k] += dynamic_vec[dp_amount - curr][k - 1];
                }
            }

            //for (auto& min_vec:dynamic_vec)
            //{
	           // for (auto&num:min_vec)
	           // {
            //        cout << num << ' ';
	           // }
            //    cout << '\n';
            //}
            //cout << '\n';
        }

        

        cout << dynamic_vec[amount][limit];
        //Solution01
    }
};


/*
 一个设备由N种类型元器件组成(每种类型元器件只需要一个，
 类型type编号从0~N-1,每个元器件均有可靠性属性reliability，
 可靠性越高的器件其价格price越贵
 而设备的可靠性由组成设备的所有器件中可靠性最低的器件决定
 给定预算S，购买N种元器件(每种类型元器件都需要购买一个)
 不超过预算，最大可靠性

输入描述
S N，其中S为总的预算，N元器件的种类
total，表示元器件的总数，每种型号的元器件可以有多种
此后输入有total行具体器件的数据
type reliability price
其中type为整数类型，代表元器件的类型编号从0 ~ N-1；
reliabily 整数类型，代表元器件的可靠性；
price 整数类型，代表元器件的价格

输出描述
符合预算的设备的最大可靠性，如果预算无法买产N种器件，则返回-1

示例1
500 3
6
0 80 100
0 90 200
1 50 50
1 70 210
2 50 100
2 60 150
输出
60

预算500，设备需要3种元件组成：
方案类型0的第一个(可靠性80)，
类型1的第二个(可靠性70)，
类型2的第二个(可靠性60)，
可以使设备的可靠性最大 60
 */
class Solution02
{
public:
    unordered_map<int, vector<vector<int>>>device_map;
    Solution02(vector<vector<int>>&num_vec, int total_amount, int kind)
    {
        for (auto&min_vec:num_vec)
        {
            int kind = min_vec[0];
            vector<int>value_vec=min_vec;
            device_map[kind].push_back(value_vec);
        }
        //0 kind 1value 2amount
        //int curr_amount=device_map[k-1][i][2]
    	//int curr_value=device_map[k-1][i][1]
        //dp[k][amount]=dp[k-1][amount-curr_amount]+curr_value
        //kind i value amount
        //1层k, 2层item
        vector<vector<vector<int>>>dynamic_vec;

        //只选择0的时候，价格
        vector<vector<int>>kind0_vec = device_map[0];
        int v0_size = kind0_vec.size();
        vector<vector<int>>dp_vec0;
        for (int i=0; i<v0_size; i++)
        {
            //0 kind 1value 2amount
            int kind0_value = kind0_vec[i][1];
            int kind0_amount = kind0_vec[i][2];
            if (kind0_amount<= total_amount)
            {
                vector<int>vec0_i = { 0, kind0_value, kind0_amount };
                dp_vec0.push_back(vec0_i);
            }
        }
        dynamic_vec.push_back(dp_vec0);
        //转移方程
        for (int k=1; k<=kind-1; k++)
        {
            vector<vector<int>>vec_k;
            //0 kind 1value 2amount
            for (auto&curr_kind:device_map[k])
            {
                int curr_value = curr_kind[1];
                int curr_amount = curr_kind[2];

                for (auto& prev_vec_i: dynamic_vec[k - 1])
                {
                    int prev_value = prev_vec_i[1];
                    int prev_amount = prev_vec_i[2];

                    if (curr_amount+prev_amount<=total_amount)
                    {
                        vector<int>vec_k_i = { k, min(curr_value, prev_value), curr_amount + prev_amount };
                        vec_k.push_back(vec_k_i);
                    }
                }
            }
            dynamic_vec.push_back(vec_k);
        }

        
        if (dynamic_vec.size()<kind || dynamic_vec[kind-1].empty())
        {
            cout << -1;
            return;
        }

        int result = 0;
        for (auto& value_item : dynamic_vec[kind - 1])
        {
            result = max(result, value_item[1]);
        }

        cout << result;
        //Solution02
    }
};

int main()
{
	{
/*
500 3
6
0 80 100
0 90 200
1 50 50
1 70 210
2 50 100
2 60 150

5 3
6
0 80 100
0 90 200
1 50 50
1 70 210
2 50 100
2 60 150
*/
        int total_amount, kind, v_size;
        cin >> total_amount >> kind >> v_size;
        cin.ignore();

        vector<vector<int>>num_vec;
        for (int i=0; i<v_size; i++)
        {
            string input;
            getline(cin, input);
            string token;
            stringstream oh_sstream(input);

            vector<int>min_vec;
            while (oh_sstream>>token)
            {
                min_vec.push_back(stoi(token));
            }
            num_vec.push_back(min_vec);
        }

        Solution02 solu(num_vec, total_amount, kind);

        return 0;
	}
/*
4 3 2 4_n总数  3_和为t 2_k个运动
1 1 2 3
*/
    int v_size, amount, limit;
    cin >> v_size >> amount >> limit;

    vector<int>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> num_vec[i];
    }

    Solution01 solu(num_vec, amount, limit);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
